package com.heima.leetcode.datastructure.deque;

import com.heima.datastructure.deque.ArrayDeque1;
import com.heima.datastructure.deque.LinkedListDeque;
import com.heima.datastructure.queue.LinkedListQueue;


import java.util.*;

/**
 * 二叉树z字层序遍历
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/2 11:11
 */
public class ZigzagLevelOrder {
    /*
               1
              / \
             2   3
            / \ / \
           4  5 6  7
           ...

           1
           3 2
           4 5 6 7
           ....
     */
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root){
        if (root == null){
            return Collections.emptyList();
        }
        List<List<Integer>> result = new ArrayList<>();
        LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
        queue.offer(root);
        int curLevel = 1; // 当前层节点数量
        int nextLevel = 0; // 下一层节点数量
        int level = 1; // 用来判断层的奇偶
        while (!queue.isEmpty()){
            LinkedList<Integer> deque = new LinkedList<>(); // 用的java提供的双端队列
            // 遍历当前层节点
            for (int i = 0; i < curLevel; i++) {
                if (queue.peek() != null){
                    TreeNode node = queue.poll();
                    if (node.left != null){
                        queue.offer(node.left);
                        nextLevel++;
                    }
                    if (node.right != null){
                        queue.offer(node.right);
                        nextLevel++;
                    }
                    if (isOdd(level)){
                        deque.offerLast(node.value);
                    }else{
                        deque.offerFirst(node.value);
                    }
                }
            }
            result.add(deque);
            curLevel = nextLevel;
            nextLevel = 0;
            level++;
        }
        return result;
    }
    private static boolean isOdd(int number){
        return (number & 1) == 1;
    }
}
